package n146;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 苏文广
 * @since 2023/4/19
 */
public class Solution {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.get(1);
        lruCache.put(3,3);
        lruCache.get(2);

    }

    static class LRUCache {
        Map<Integer, Node> map;
        Node head;
        Node tail;
        int capacity;
        int size;


        public LRUCache(int capacity) {
            map = new HashMap<>(capacity);
            this.capacity = capacity;
            this.head = new Node(-1,-1);
            this.tail = new Node(-2,-2);
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            // 1. 获取值
            Node node = map.get(key);
            if (node == null) {
                return -1;
            }
            deleteNode(node);
            moveHead(node);
            return node.value;

        }

        private void moveHead(Node node) {
            Node headNext = head.next;
            headNext.pre = node;
            head.next =  node;

            node.pre = head;
            node.next  = headNext;
        }

        public void put(int key, int value) {
            // 1. 没达到容量, 添加节点
            Node node = map.get(key);
            if (node == null && size < capacity) {
                Node newNode = new Node(key, value);
                addNode(newNode);
                return;
            }

            // 2. 已达到容量,需要淘汰
            if (node == null && size == capacity) {
                Node pre = tail.pre;
                deleteNode(pre);
                map.remove(pre.key);
                size--;

                addNode(new Node(key,value));
            }
            // 3. 相同数据,更新值
            if (node != null) {
                node.value = value;
                deleteNode(node);
                moveHead(node);
            }
        }

        private void deleteNode(Node node) {
            Node next = node.next;
            next.pre = node.pre;
            node.pre.next = next;
        }

        private void addNode(Node node) {
            // 维护链表
            Node next = head.next;
            node.next = next;
            next.pre = node;

            head.next = node;
            node.pre = head;

            // 加入map
            map.put(node.key, node);
            size++;
        }

        class Node {
            int key;
            int value;
            Node pre;
            Node next;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    }
}
